import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution1307 {

    boolean ans=false;

    public boolean isSolvable(String[] words, String result) {
        int[] map=new int[26];
        Arrays.fill(map,-1);
        int count=0;
        for (String word : words) {
            for (char c : word.toCharArray()) {
                if (map[c-'A']==-1){
                    map[c-'A']=count;
                    count++;
                }
            }
        }
        for (char c : result.toCharArray()) {
            if (map[c-'A']==-1){
                map[c-'A']=count;
                count++;
            }
        }
        int[] f=new int[count];
        boolean[] visit=new boolean[10];
        Set<Integer> set=new HashSet<>();
        for (String word : words) {
            if (word.length()>1){
                set.add(map[word.charAt(0)-'A']);
            }
        }
        if (result.length()>1){
            set.add(map[result.charAt(0)-'A']);
        }
        dfs(visit,f,words,result,map,0,set);
        return ans;
    }

    private void dfs(boolean[] visit, int[] f, String[] words, String result, int[] map, int k, Set<Integer> set) {
        if (k==f.length){
            if (check(f,map,words,result) && !ans){
                ans=true;
            }
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (!visit[i] && (i!=0||!set.contains(k))){
                f[k]=i;
                visit[i]=true;
                dfs(visit,f,words,result,map,k+1, set);
                if (ans){
                    return;
                }
                visit[i]=false;
            }
        }
    }

    private boolean check(int[] f, int[] map, String[] words, String result) {
        int a=0;
        for (String word : words) {
            a+=deal(word,map,f);
        }
        return a==deal(result,map,f);
    }

    private int deal(String result, int[] map, int[] f) {
        int t=0;
        for (char c : result.toCharArray()) {
            t=t*10+f[map[c-'A']];
        }
        return t;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1307().isSolvable(new String[]{"THAT","IS","WHY","IT","IS"},"FALSE"));
    }
}
